package leetcode_700;

/**
 *@author 周杨
 *RedundantConnectionII_685 有向图多余边的查找
 *describe:用并查集 AC 45% 
 *see:https://leetcode.com/problems/redundant-connection-ii/discuss/170663/Java-Union-Find-solution-with-explanation
 *2018年10月7日 下午4:48:27
 */
public class RedundantConnectionII_685 {
	 public int[] findRedundantDirectedConnection(int[][] edges) {
	        int m = edges.length;
	        int[] parent = new int[m + 1];
	        int[] res1 = new int[2];
	        int[] res2 = new int[2];
	        for (int[] edge : edges) {
	            int from = edge[0];
	            int to = edge[1];
	            if (parent[to] == 0) {
	                parent[to] = from;
	            } else {
	                res2 = new int[] {from, to};
	                res1 = new int[] {parent[to], to};
	                break;
	            }
	        }
	        parent = new int[m + 1];
	        for (int i = 1; i <= m; i++) {
	            parent[i] = i;
	        }
	        for (int[] edge : edges) {
	            int from = edge[0];
	            int to = edge[1];
	            if (from == res2[0] && to == res2[1]) continue;
	            int r1 = findRoot(from, parent);
	            int r2 = findRoot(to, parent);
	            if (r1 == r2) { //from and to has already been connect to the same root
	                if (res1[0] == 0) return new int[] {from, to};
	                else return res1;
	            }
	            parent[to] = from;
	        }
	        return res2;
	    }
	    private int findRoot(int v, int[] parent) {
	        while (v != parent[v]) {
	            parent[v] = parent[parent[v]];
	            v = parent[v];
	        }
	        return v;
	    }
}
